package Top_Interview_Questions_Review._001Tree;



import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/10 12:37
 * <p>
 * 这题不限制你用先序遍历,还是用层序遍历
 */
public class _0297 {
    /**
     *        1
     *       / \
     *      2   5
     *     / \
     *    3  4
     */
    public static void main(String[] args) {

        _0297 test = new _0297();
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        //1,2,3,null,null,4,null,null,5,null,null,
        String serialize = test.serialize(root);

        TreeNode node = test.deserialize(serialize);
        System.out.println(serialize);
    }

    

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    //1,2,3,null,null,4,null,null,5,null,null,
    public String rserialize(TreeNode root, String str) {
        // Recursive serialization.
        if (root == null) {
            str += "null,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
        return rdeserialize(data_list);
    }
    //1,2,3,null,null,4,null,null,5,null,null,
    public TreeNode rdeserialize(List<String> l) {
        // Recursive deserialization.
        if (l.get(0).equals("null")) {
            l.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
        l.remove(0);
        root.left = rdeserialize(l);
        root.right = rdeserialize(l);

        return root;
    }

}
